/*
题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式
一行，若干个整数，中间由空格隔开。

输出格式
两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出样例

输入
389 207 155 300 299 170 158 65
输出
6
2
*/

#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define all(rq) rq.begin(),rq.end()
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)

using namespace std;
const int INF=0x3f3f3f3f;

int main(){
	string str;
	getline(cin,str);
	istringstream iss(str);
	vector<int> a;
	int num;
	while(iss>>num){
		a.emplace_back(num);
	}
	
	vector<int> f(a.size()+1); //f[i]为长度为子序列中最后最高的高度 递减
	vector<int> t(a.size()+1); //t[i]为第i号导弹系统的拦截的最后一个导弹的高度 递增
	f[0]=INF;
	int l=0,r=0;
	int cnt=1;
	t[1]=a[0]; 

	for(int i=0;i<a.size();i++){
		if(i){ //二分搜索找到已有导弹系统最后一个导弹的高度刚好大于当前所枚举的导弹 若有则更新当前导弹系统的最后一枚导弹的高度 否则增加导弹系统
			int ans=-1,l1=1,r1=cnt;
			while(r1>=l1){
				int mid=(l1+r1)/2;
				
				if(t[mid]>=a[i]){
					ans=mid;
					r1=mid-1;
				}else{
					l1=mid+1;
				}
			}
			
			if(ans==-1){
				cnt++;
				t[cnt]=a[i];
			}else{
				t[ans]=a[i];
			}
		}
		
		int ans=-1,l0=l,r0=r;
		while(r0>=l0){ //二分搜索找到当前已有长度的子序列中最后一个高度刚好大于等于当前所枚举的元素 若增加长度比所记录最大长度大则更新最大长度
			int mid=(l0+r0)/2;
			
			if(f[mid]>=a[i]){
				ans=mid;
				l0=mid+1;
			}else{
				r0=mid-1;
			}
		}
		
		f[ans+1]=max(a[i],f[ans+1]);
		r=max(r,ans+1);
	}
	
	
	cout<<r<<endl<<cnt<<endl;
	return 0;
}